/*
200. 岛屿数量
给定一个由'1'（陆地）和'0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
输入:
11000
11000
00100
00011
输出: 3

思路:
1. DFS: 遍历这个二维数组，走过一个点，如果是1，标记一下(比如变成2)，然后走他的上下左右(借助栈或者递归，入栈一个节点，while栈不为空，弹出一个节点，操作后将它下一个没有入栈过的邻节点入栈)
2. BFS: 借助辅助队列,从源节点开始依次按照宽度进队列，然后弹出，每弹出一个点，把该节点所有没有进过队列的邻接点放入队列，直到队列变空
 */

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let counts = 0
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] === '1') {
        counts++
      }
      DFSIslands(grid, row, col)
    }
  }
  return counts
}

/**
 * @param {character[][]} grid
 * @param {number} row: current position
 * @param {number} col: current position
 */
function DFSIslands (grid, row, col) {
  const rows = grid.length
  const cols = grid[0].length
  // 边界和非陆地 跳过
  if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] !== '1') {
    return
  }
  // 标记
  grid[row][col] = '2'
  DFSIslands(grid, row - 1, col)
  DFSIslands(grid, row + 1, col)
  DFSIslands(grid, row, col - 1)
  DFSIslands(grid, row, col + 1)
}

/**
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands2 (grid) {
  if (!grid.length || !grid[0].length) {
    return 0
  }
  const rows = grid.length
  const cols = grid[0].length
  let counts = 0
  const queue = []
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        counts++
        queue.push([row, col])
        while (queue.length) {
          const [tempRow, tempCol] = queue.shift()
          if (grid[tempRow][tempCol] === '1') {
            grid[tempRow][tempCol] = '#' // 标记
            // 添加上下左右四个节点
            if (tempRow - 1 >= 0 && grid[tempRow - 1][tempCol] === '1') {
              queue.push([tempRow - 1, tempCol])
            }
            if (tempRow + 1 < rows && grid[tempRow + 1][tempCol] === '1') {
              queue.push([tempRow + 1, tempCol])
            }
            if (tempCol - 1 >= 0 && grid[tempRow][tempCol - 1] === '1') {
              queue.push([tempRow, tempCol - 1])
            }
            if (tempCol + 1 < cols && grid[tempRow][tempCol + 1] === '1') {
              queue.push([tempRow, tempCol + 1])
            }
          }
        }
      }
    }
  }
  return counts
}

const arr = [
  ['1', '1', '1'],
  ['0', '1', '0'],
  ['1', '1', '1']
]
console.log(numIslands2(arr))
